using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Reflection;
using System.Diagnostics;

namespace Dida
{
	public class HashSet<T> : ISet<T>, ICloneable
	{
		IEqualityComparer<T> comparer;
		
		Bucket[] buckets;
		int count;

		public HashSet()
			: this(EqualityComparer<T>.Default)
		{			
		}

		public HashSet(IEqualityComparer<T> comparer)
		{
			this.comparer = comparer;

			buckets = new Bucket[16];
			count = 0;
		}

		public HashSet(IEnumerable<T> src)
		{
			comparer = EqualityComparer<T>.Default;

			if (src is HashSet<T> && ((HashSet<T>)src).comparer == comparer)
			{
				// src is a hash set aswell, and it uses the same comparer,
				// so we can just copy the internal data directly.

				HashSet<T> srcHashset = (HashSet<T>)src;

				comparer = srcHashset.comparer;
				count = srcHashset.count;

				buckets = new Bucket[srcHashset.buckets.Length];
				for (int i = 0; i < srcHashset.buckets.Length; i++)
				{
					Item prev = null;
					for (Item cur = srcHashset.buckets[i].firstItem; cur != null; cur = cur.next)
					{
						Item clone = new Item();
						clone.hash = cur.hash;
						clone.value = cur.value;

						if (prev == null)
							buckets[i].firstItem = cur;
						else
							prev.next = cur;
						prev = cur;
					}
				}
			}
			else
			{
				int reserve = 16;

				// if it's an ICollection, we can get the size, and with that,
				// we can reserve the currect amount of buckets.
				if (src is ICollection<T>)
				{
					ICollection<T> collection = (ICollection<T>)src;
					int srcCount = collection.Count;
					reserve = 1;
					while (srcCount != 0)
					{
						srcCount >>= 1;
						reserve <<= 1;
					}
				}

				buckets = new Bucket[reserve];
				count = 0;

				foreach (T item in src)
					Add(item);
			}
		}

		private void Resize(int newSize)
		{
			Bucket[] newBuckets = new Bucket[newSize];
			foreach (Bucket bucket in buckets)
			{
				Item next;
				for (Item item = bucket.firstItem; item != null; item = next)
				{
					next = item.next;
					item.next = null;

					newBuckets[item.hash & (newBuckets.Length - 1)].InsertItem(this, item);
				}
			}

			buckets = newBuckets;
		}

		private void Grow()
		{
			Resize(buckets.Length * 2);
		}

		private void Shrink()
		{
			Resize(buckets.Length / 2);
		}

		/// <summary>
		/// Adds the given value to this set. If the given item is already part of the set
		/// (or an item that equals this value according to the current 
		/// <see cref = "IEqualityComparer&lt;T>"/>, the only the old value 
		/// will be kept.
		/// </summary>
		/// <param name="value">The value you want to add</param>
		/// <returns>true if successfully added, false if the item was 
		/// already part of the set</returns>
		public bool Add(T value)
		{
			Item item = new Item();
			item.value = value;
			item.hash = comparer.GetHashCode(value);

			if (buckets[item.hash & (buckets.Length - 1)].InsertItem(this,item))
			{
				count++;

				if (count > (int)(buckets.Length * 1.5f))
					Grow();

#if DEBUG
				Debug.Assert(CalcCount() == count, "HashSet is corrupted");
#endif
				return true;
			}
			else
				return false;
		}

		public bool Remove(T item)
		{
			int hashCode = item.GetHashCode() & (buckets.Length - 1);
			if (buckets[hashCode].Remove(this, item))
			{
				count--;

				if (count < (int)(buckets.Length * .5f) & buckets.Length > 16)
					Shrink();

#if DEBUG
				Debug.Assert(CalcCount() == count, "HashSet is corrupted");
#endif
				return true;
			}
			else
				return false;
		}

		void ICollection<T>.Add(T item)
		{
			Add(item);
		}

		public void Clear()
		{
			buckets = new Bucket[16];
			count = 0;
		}

		public bool Contains(T item)
		{
			if (item != null)
			{
				int bucket = comparer.GetHashCode(item) & (buckets.Length - 1);
				return buckets[bucket].Contains(this, item);
			}
			else
				return false;
		}

		public void CopyTo(T[] array, int arrayIndex)
		{
			foreach(T val in this)
				array[arrayIndex++] = val;
		}

		void ICollection.CopyTo(Array arr,int writePtr)
		{
			CopyTo((T[])arr, writePtr);
		}

		public int Count
		{
			get { return count; }
		}

		public bool IsReadOnly
		{
			get { return false; }
		}

		public IEnumerator<T> GetEnumerator()
		{
			return new Enumerator(this);
		}

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return new Enumerator(this);
		}

		public bool IsSynchronized
		{
			get { return false; }
		}

		public object SyncRoot
		{
			get { return this; }
		}

		public HashSet<T> GetDifference(ISet<T> b)
		{
			HashSet<T> ret = new HashSet<T>();

			foreach (Bucket curBucket in buckets)
			{
				for (Item cur = curBucket.firstItem; cur != null; cur = cur.next)
				{
					if (!b.Contains(cur.value))
						ret.Add(cur.value);
				}
			}

			return ret;
		}

		ISet<T> ISet<T>.GetDifference(ISet<T> b)
		{
			return GetDifference(b);
		}

		public HashSet<T> GetIntersection(ISet<T> b)
		{
			if (b is HashSet<T>)
			{
				HashSet<T> bAsHashSet = (HashSet<T>)b;
				if(comparer == bAsHashSet.comparer)
					return GetIntersectionHashSets(bAsHashSet);
			}

			HashSet<T> ret = new HashSet<T>(comparer);

			foreach (Bucket curBucket in buckets)
			{
				for (Item cur = curBucket.firstItem; cur != null; cur = cur.next)
				{
					if (b.Contains(cur.value))
						ret.Add(cur.value);
				}
			}

			return ret;
		}

		private HashSet<T> GetIntersectionHashSets(HashSet<T> b)
		{
			Debug.Assert((buckets.Length & (buckets.Length - 1)) == 0,"The bucket count must always be a power of two");
			Debug.Assert((b.buckets.Length & (b.buckets.Length - 1)) == 0, "The bucket count must always be a power of two");
			Debug.Assert(comparer == b.comparer);

			HashSet<T> ret = new HashSet<T>(comparer);

			HashSet<T> big, small;
			if (buckets.Length > b.buckets.Length)
			{
				big = this;
				small = b;
			}
			else
			{
				big = b;
				small = this;
			}

			int numShifts = (int)FastLog2((uint)(big.buckets.Length - small.buckets.Length));

			for (int i = 0; i < big.buckets.Length; i++)
			{
				int smallIndex = i >> numShifts;
				Bucket otherBucket = small.buckets[smallIndex];
				
				for (Item item = big.buckets[i].firstItem; item != null; item = item.next)
				{
					for (Item otherItem = otherBucket.firstItem; otherItem != null; otherItem = otherItem.next)
					{
						if (item.hash == otherItem.hash &&
							comparer.Equals(item.value, otherItem.value))
						{
							ret.Add(item.value);
							break;
						}
					}
				}
			}

			return ret;
		}

		private UInt32 FastLog2(UInt32 val)
		{
			UInt32 ret = 0;
			if ((val & 0xffff0000) != 0)
				ret += 16;
			if ((val & 0xff00ff00) != 0)
				val += 8;
			if ((val & 0xf0f0f0f0) != 0)
				val += 4;
			if ((val & 0xcccccccc) != 0)
				val += 2;
			if ((val & 0xaaaaaaaa) != 0)
				val++;
			return val;
		}

#if DEBUG
		private int CalcCount()
		{
			int ret = 0;
			foreach (Bucket bucket in buckets)
			{
				for (Item i = bucket.firstItem; i != null; i = i.next)
					ret++;
			}

			return ret;
		}
#endif

		struct Bucket
		{
			public Item firstItem;

			public bool InsertItem(HashSet<T> set,Item item)
			{
				if (firstItem == null)
				{
					firstItem = item;
					return true;
				}
				else
				{
					// test if the item already exists
					Item prev = null;
					for (Item cur = firstItem; cur != null; cur = cur.next)
					{
						if (set.comparer.Equals(item.value,cur.value))
							return false;
						prev = cur;
					}

					prev.next = item;
					return true;
				}
			}

			public bool Contains(HashSet<T> set,T value)
			{
				for (Item cur = firstItem; cur != null; cur = cur.next)
					if (set.comparer.Equals(value, cur.value))
						return true;
				return false;
			}

			public bool Remove(HashSet<T> set,T value)
			{
				Item prev = null;
				for (Item cur = firstItem; cur != null; cur = cur.next)
				{
					if (set.comparer.Equals(value, cur.value))
					{
						if (prev == null)
							firstItem = cur.next;
						else
							prev.next = cur.next;

						return true;
					}
					prev = cur;
				}
				return false;
			}
		}

		class Item
		{
			public T value;
			public int hash;

			public Item next;
		}

		class Enumerator : IEnumerator<T>
		{
			HashSet<T> set;
			int bucket;
			Item item;

			public Enumerator(HashSet<T> set)
			{
				this.set = set;

				bucket = -1;
				item = null;
			}
			
			public T Current
			{
				get { return item.value; }
			}

			public void Dispose()
			{
				// nothing
			}

			object System.Collections.IEnumerator.Current
			{
				get { return item.value; }
			}

			public bool MoveNext()
			{
				if (item != null)
					item = item.next;
				
				while (item == null)
				{
					bucket++;
					if (bucket >= set.buckets.Length)
						return false;

					item = set.buckets[bucket].firstItem;
				}

				return true;
			}

			public void Reset()
			{
				bucket = -1;
				item = null;
			}
		}

		#region ICloneable Members

		public HashSet<T> Clone()
		{
			return new HashSet<T>(this);
		}

		object ICloneable.Clone()
		{
			return Clone();			
		}

		#endregion
	}
}
